#include<bits/stdc++.h>

#define re read()
#define lol long long
using namespace std;

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);return x*sgn;}

const int MAXN=10010;
int n,m,A[MAXN];
struct SEGTREE{
	lol sum,maxn,maxl,maxr;
	void PUSHUP(SEGTREE ll,SEGTREE rr){
		sum=ll.sum + rr.sum;
		maxl=max(ll.maxl,ll.sum + rr.maxl);
		maxr=max(rr.maxr,rr.sum + ll.maxr);
		maxn=max(ll.maxn,max(rr.maxn,ll.maxr + rr.maxl));
	}
	void clear(){sum = maxn = maxl = maxr = 0;}
}tr[MAXN<<2];

void BUILD(int k,int l,int r){
	if(l==r){
		tr[k].sum = tr[k].maxn = tr[k].maxl = tr[k].maxr = A[l];
		return;
	}
	int mid=(l+r)>>1;
	BUILD(k<<1,l,mid); BUILD(k<<1|1,mid+1,r);
	tr[k].PUSHUP(tr[k<<1],tr[k<<1|1]);
	return;
}

SEGTREE GET(int k,int xl,int xr,int l = 1,int r = n){
	if(xl>xr){SEGTREE ans;ans.clear(); return ans;}
	if(xl == l && xr == r) return tr[k];
	int mid = l+r>>1;
	if(xr <= mid) return GET(k<<1,xl,xr,l,mid);
	else if(xl > mid) return GET(k<<1|1,xl,xr,mid+1,r);
	else {
		SEGTREE ans; ans.PUSHUP(GET(k<<1,xl,mid,l,mid),GET(k<<1|1,mid+1,xr,mid+1,r));
		return ans;
	}
}

int main(){
	int casenum=re;
	while(casenum--){
		n=re;
		for(int i=1;i<=n;i++) A[i]=re;
		BUILD(1,1,n);
		m=re;
		while(m--){
			int a1=re,a2=re,a3=re,a4=re;
			if(a2 < a3){
                lol ans = GET(1,a1,a2).maxr + GET(1,a2+1,a3-1).sum + GET(1,a3,a4).maxl;
				printf("%lld\n",ans);
            }
			else{
				lol ans=GET(1,a3,a2).maxn;
				if(a1 < a3) ans=max(ans,GET(1,a1,a3-1).maxr+GET(1,a3,a4).maxl);
				if(a2 < a4) ans=max(ans,GET(1,a1,a2).maxr+GET(1,a2+1,a4).maxl);
				printf("%lld\n",ans);
			}
		}
	}
	return 0;
}
